Three-dimensional (3-D) data provides an important source of information for generating realistic computer models of real-world objects. For example, biological and geophysical data is often captured using volumetric scanning methods such as magnetic resonance imaging (MRI) or ultrasound. The data from these devices is usually stored as a regular grid of values that provide information about the surface of the scanned object and its detailed internal structure. Most objects, natural or man-made, contain multiple elements, possibly formed of different elements, with vastly different physical properties that are typically organized in complicated geometric configurations. Extracting precise geometric models of the interfaces between these elements is important both for visualization and for realistic physically-based simulations in a variety of fields, from biomedical computing and computer animation to oil-and-gas exploration and engineering.
Multi-element volumes impose particular challenges for sampling and meshing algorithms because the boundaries between elements are typically not smooth manifolds. As a result, intersections of elements can produce sharp features such as edges and corners. Furthermore, the development of increasingly realistic simulations dictates additional constraints, such as a sufficient number of samples to accurately represent the geometry, compact sets of nearly regular triangles, and consistent tessellations across element boundaries.
The problem of body fitting meshes that are both adaptive and geometrically accurate is important in a variety of biomedical applications in a multitude of clinical settings, including electrocardiology, neurology, and orthopedics. Adaptivity is necessary because of the combination of large-scale and smallscale structures (e.g. relatively small blood vessels spanning a human head). Geometric accuracy is important for several reasons. In some cases, such as computational fluid dynamics, the fine-scale structure of the fluid domain is important for qualitative and quantitative accuracy of the solutions. More generally, finite element approximations of elliptic problems with rough coefficients require increased spatial resolution normal to element boundaries. The problem of constructing meshes from biomedical 3-Ds is particularly difficult because of the complexity and irregularity of the structures, and thus tuning or correcting meshes by hand is quite difficult and time consuming. Many researchers and commercial products simply subdivide the underlying hexahedral 3-D grid and assign element properties to tetrahedral based on standard decomposition of each hexahedron into tetrahedral which fails to provide the needed adaptivity and geometric accuracy.